package com.yulongtian.offers.day202209.day20220923;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/?favorite=xb9nqhhg
 *
 * @author YulongTian
 * @date 2022/9/23 - 16:09
 */
public class Test04 {
    public static void main(String[] args) {
        int[][] matrix={{1,2,3},{4,5,6},{7,8,9}};
        List<Integer> list = spiralOrder(matrix);
        System.out.println(list.toString());
    }

    //输出一维数组
    public static void show_one_arr(int[] arr){
        for (int i : arr) {
            System.out.print(i+",");
        }
        System.out.println();
    }

    public static List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return new ArrayList<>();
        }
        int n = matrix[0].length;
        List<Integer> res=new ArrayList<>();
        if (m == 1) {
            for(int i=0;i<n;i++){
                res.add(matrix[0][i]);
            }
            return res;
        }

        if (n == 1) {
            for (int i = 0; i < m; i++) {
                res.add(matrix[i][0]);
            }
            return res;
        }
        int index = 0;

        int i = 0;
        int j = 0;

        while (index < m * n) {
            //向右
            for (int p = j; ; p++) {
                if (p == n || matrix[i][p] == Integer.MAX_VALUE) {
                    j = p - 1;
                    break;
                }
                res.add(matrix[i][p]);
                index++;
                matrix[i][p] = Integer.MAX_VALUE;
            }
            i++;
            //向下
            for (int q = i; ; q++) {
                if (q == m || matrix[q][j] == Integer.MAX_VALUE) {
                    i = q - 1;
                    break;
                }
                res.add(matrix[q][j]);
                index++;
                matrix[q][j] = Integer.MAX_VALUE;
            }
            j--;
            //向左
            for (int p = j; ; p--) {
                if(p==-1||matrix[i][p]==Integer.MAX_VALUE){
                    j=p+1;
                    break;
                }
                res.add(matrix[i][p]);
                index++;
                matrix[i][p]=Integer.MAX_VALUE;
            }
            i--;
            //向上
            for(int p=i;;p--){
                if(p==-1||matrix[p][j]==Integer.MAX_VALUE){
                    i=p+1;
                    break;
                }
                res.add(matrix[p][j]);
                index++;
                matrix[p][j]=Integer.MAX_VALUE;
            }
            j++;
        }
        return res;
    }
}
